package practice;

import java.util.Stack;

/**
 * 给定一个仅包含 0 和 1 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
 * 输入:
 * [
 * ["1","0","1","0","0"],
 * ["1","0","1","1","1"],
 * ["1","1","1","1","1"],
 * ["1","0","0","1","0"]
 * ]
 * 输出: 6
 */
public class _85_MaximalRectangle {
    public static void main(String[] args) {
        char[][] a = {{'0','1','1','0','1','1','1','1','1','1','1','1','1','1','1','1','1','1','0'},{'1','0','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1'},{'1','1','0','1','1','1','1','1','1','1','1','1','0','1','1','1','1','1','1'},{'1','1','1','1','1','1','1','1','1','1','1','1','1','0','1','1','1','1','1'},{'1','1','1','1','1','1','1','1','1','1','1','1','1','1','0','1','1','1','1'},{'1','1','1','0','1','1','1','0','1','1','1','1','1','1','1','1','1','0','1'},{'1','0','1','1','1','1','1','1','1','1','1','1','1','1','0','1','1','1','1'},{'1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','0','1','1','0'},{'0','0','1','1','1','1','1','1','1','1','1','1','1','1','1','0','1','1','1'},{'1','1','0','1','1','1','1','1','1','1','0','1','1','1','1','1','1','1','1'},{'1','1','1','1','1','1','1','1','1','0','1','1','1','1','1','1','1','1','1'},{'0','1','1','0','1','1','1','0','1','1','1','1','1','1','1','1','1','1','1'},{'1','1','1','1','0','1','1','1','1','1','1','1','1','1','0','1','1','1','1'},{'1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1'},{'1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1'},{'1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','0','1'},{'1','1','1','1','1','1','1','1','0','1','1','0','1','1','0','1','1','1','1'},{'1','1','1','1','1','1','0','1','1','1','1','1','1','1','1','0','1','1','1'}};
        System.out.println(new _85_MaximalRectangle().maximalRectangleByStack(a));
    }

    /**
     * 借鉴思路：
     * 使用单调栈
     */
    public int maximalRectangleByStack(char[][] matrix) {
        int n = matrix.length;
        if (n == 0) {
            return 0;
        }
        int m = matrix[0].length;
        int[] heights = new int[m + 1];
        Stack<Integer> stk = new Stack<>();
        int ans = 0, cur, w, pos;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (matrix[i][j] == '1') {
                    heights[j] += 1;
                } else {
                    heights[j] = 0;
                }
                System.out.print(heights[j] + " ");
            }
            System.out.println();
            pos = 0;
            stk.clear();
            while (pos <= m) {
                if (stk.isEmpty() || heights[pos] > heights[stk.peek()]) {
                    //  如果为空或者比之前大，入栈，指针右移
                    stk.push(pos++);
                } else {
                    // 否则，计算之前矩形面积
                    // 取当前坐标
                    cur = stk.pop();
                    // 当前宽度，如果栈为空，说明当前高度为目前中最低的坐标，宽为当前坐标(p  os)；
                    // 否则之前还有更低的坐标，宽为最高坐标（pos-1)到当前坐标的差值
                    w = stk.isEmpty() ? pos : pos - stk.peek() - 1;
                    ans = Math.max(ans, heights[cur] * w);
                    if(heights[cur] * w == 51) System.out.println("--"+cur);
                }
            }
        }
        return ans;
    }

    /**
     * 个人思路：
     * 使用暴力查找，遍历所有元素并计算当前元素能构成的最大面积
     *
     * @param matrix
     * @return
     */
    public int maximalRectangle(char[][] matrix) {
        if (matrix.length <= 0 || matrix[0].length <= 0) {
            return 0;
        }
        int result = 0;
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                if (matrix[i][j] == '1') {
                    //上面的元素和上面右边元素为1，说明当前元素在大的矩形里，可以跳过
//                    if (i > 0 && j < matrix[i].length - 1 && matrix[i - 1][j] == '1' && matrix[i - 1][j + 1] == '1') {
//                        continue;
//                    }
                    //否则，在当前元素开始查找最大的矩形
                    int curMaxAra = maxArea(matrix, i, j);
                    System.out.println("i:" + i + " j:" + j + " value:" + curMaxAra);
                    if (curMaxAra > result) {
                        result = curMaxAra;
                    }
                }

            }
        }

        return result;
    }

    /**
     * 从当前位置开始计算最大的面积
     * 先横向查，再纵向查
     */
    private int maxArea(char[][] matrix, int i, int j) {
        int result = 1;
        int horizon;
        int vertical;
        boolean isRectangle;
        //每次循环计算当前宽的最大面积
        horizon = 1;
        vertical = 1;
        for (int k = j + 1; k < matrix[i].length; k++) {
            //为0，退出
            if (matrix[i][k] == '0') {
                break;
            }
            horizon++;
            vertical = 0;
            isRectangle = true;
            //否则，计算当前宽有多大面积
            for (int l = i; l < matrix.length; l++) {
                for (int m = j; m <= k; m++) {
                    if (matrix[l][m] == '0') {
                        isRectangle = false;
                        break;
                    }
                }
                if (!isRectangle) {
                    break;
                }
                vertical++;
                if (isRectangle) {
                    int curArea = horizon * vertical;
                    if (result < curArea) {
                        result = curArea;
                    }
                }
            }
        }

        //重新初始化
        horizon = 1;
        vertical = 1;
        //每次循环计算当前长的最大面积
        for (int k = i + 1; k < matrix.length; k++) {
            //为0，退出
            if (matrix[k][j] == '0') {
                break;
            }
            vertical++;
            horizon = 0;
            isRectangle = true;
            //否则，计算当前长有多大面积
            for (int l = j; l < matrix[k].length; l++) {
                for (int m = i; m <= k; m++) {
                    if (matrix[m][l] == '0') {
                        isRectangle = false;
                        break;
                    }
                }
                if (!isRectangle) {
                    break;
                }
                horizon++;
                if (isRectangle) {
                    int curArea = horizon * vertical;
                    if (result < curArea) {
                        result = curArea;
                    }
                }
            }
        }
        return result;
    }
}
